package offer;

public class IsSubStructure {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recursion(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }

    public boolean recursion(TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null || A.val != B.val) return false;
        return recursion(A.left, B.left) && recursion(A.right, B.right);
    }
}
